window.onload = function () {
  /**
   * 1122. 数组的相对排序
   */
  console.log(relativeSortArray([2,3,1,3,2,4,6,7,9,2,19], [2,1,4,3,9,6]))

  /**
   * 300. 最长递增子序列
   */
  console.log(lengthOfLIS([10,9,2,5,3,7,101,18]))

  /**
   * 818. 赛车
   */
  console.log(racecar(3))
}

/**
 * 1122. 数组的相对排序
 * @param {number[]} arr1
 * @param {number[]} arr2
 * @return {number[]}
 */
 var relativeSortArray = function(arr1, arr2, h = new Map) {
  arr2.forEach((v, i) => h.set(v, i))
  return sort(arr1, v => h.has(v) ? h.get(v) : 1000 + v)
};
var sort = (a, v, l = 0, r = a.length - 1) => {
  if (l === r) return
  var m = l + r >>> 1, p1 = l, p2 = m + 1, i = 0, t = []
  sort(a, v, l, m)
  sort(a, v, m + 1, r)
  while (p1 <= m || p2 <= r) {
      t[i++] = p2 > r || p1 <= m && v(a[p1]) < v(a[p2]) ? a[p1++] : a[p2++]
  }
  for(var i = 0; i < t.length; i++) a[l + i] = t[i]
  return a
}


/**
 * 300. 最长递增子序列
 * @param {number[]} nums
 * @return {number}
 */
 var lengthOfLIS = function(nums) {
  let dp = Array(nums.length).fill(1);
  let result = 1;

  for(let i = 1; i < nums.length; i++) {
      for(let j = 0; j < i; j++) {
          if(nums[i] > nums[j]) {
              dp[i] = Math.max(dp[i], dp[j]+1);
          }
      }
      result = Math.max(result, dp[i]);
  }

  return result;
};


/**
 * 818. 赛车
 * @param {number} target
 * @return {number}
 */
 var racecar = function(target) {
  let dp = [];
      for(let i = 1; i <= target; i++) {
          dp[i] = Number.MAX_VALUE;
          let j = 1, cnt1 = 1;
          for (; j < i; j = (1 << ++cnt1) - 1) {
              for (let k = 0, cnt2 = 0; k < j; k = (1 << ++cnt2) - 1) {
                  dp[i] = Math.min(dp[i], cnt1 + 1 + cnt2 + 1 + dp[i - (j - k)]);
              }
          }
  
          dp[i] = Math.min(dp[i], cnt1 + (i == j ? 0 : 1 + dp[j - i]))
      }
  
      return dp[target];
  };
